НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №3 з навчальної дисципліни “Програмування складних алгоритмів” Тема: «Методи сортування» Варіант № 15 Дата « 5 » червня 2022  Мета роботи: Метою лабораторної роботи є набуття практичних навичок з використання простих методів сортування. Лабораторна робота спирається на знаннях отриманих при вивченні наступних питань лекції: – Поняття сортування. – Різних методів сортування. Теоретичні відомості: Сортування – впорядковування за ключовими елементами структури даних, на якій визначено відношення порядку. Алгоритмом сортування називається алгоритм для впорядкування деяких елементів множини. Практично кожен алгоритм сортування можна розбити на три основних етапи: Порівняння (впорядкованість пари елементів), Перестановка (зміна місць пари елементів), Перестановка (власне алгоритм сортування. Для алгоритму сортування (як і для будь-якого іншого сучасного алгоритму) основною характеристикою є час, необхідний на впорядкування n-елементного масиву. Для значної кількості алгоритмів середній і найгірший час впорядкування n-елементного масиву є — це пов'язано з тим, що в них передбачені перестановки елементів, що стоять поряд (різниця між індексами елементів не перевищує деякого заданого числа). Такі алгоритми зазвичай є стабільними, хоча і не ефективними для великих масивів. Інший клас алгоритмів здійснює впорядкування за час . В цих алгоритмах використовується можливість обміну елементів, що знаходяться на будь-якій відстані один від одного. Cортування вставками - cуть методу полягає в тому, що на кожному кроці алгоритму вибирається один з елементів вхідних даних і вставляється його на потрібну позицію в уже відсортованому списку, до тих пір, поки набір вхідних даних не буде вичерпаний. Сортування вибором — пошук найменшого або найбільшого елемента і переміщення його в початок або кінець впорядкованого списку. Сортування обміном (Bubblesort) — для кожної пари індексів проводиться обмін, якщо елементи розташовані не по порядку. Та купа інших методів сортування. Завдання на лабораторну роботу: 1. Провести сортування масивів вказаним методом та у вказаному порядку. Для тестування алгоритмів сортування масив (10x10, та більше бажанням). 2. Самостійно обрати додатковий метод та провести сортування того ж масиву. 3. Порівняти кількість перестановок (або час виконання) обох методів. Спробувати порівняти час виконання сортування з масивом більшого розміру, який створити за допомогою генератора випадкових чисел / Як перше сортування було виконане сортування вставками, а для порівняння вже було написане сортування бульбашкою. Результати виконання: Розмір Час виконання(Insert sort) Час виконання(Bubble sort)  10x10 1300 нс 10300 нс  50x50 39600 нс 5721700 нс  100x100 258200 нс 93991700 нс   / / Посилання на Replit: https://replit.com/join/kllbnwxfnf-tr-15fundamient Висновок: Під час виконання даної лабораторної роботи було набуто практичних навичок з використання методів сортування, а саме, завдання було виконано за допомогою методів сортування вставкавами, там бульбашкою. Для порівняння їх між собою було складено таблицю із замірами часу сортування різного розміру матриць. Копія коду: #include <iostream> #include <chrono> #include <ctime> using namespace std; int main() { srand(time(NULL)); int matSize; cout << "Enter matrix size:\n"; cin >> matSize; int mat[matSize][matSize]; int mat1[matSize][matSize]; //input for(int i = 0; i < matSize; i++) { for(int j = 0; j < matSize; j++) { mat[i][j] = rand() % 62 + (-30); } } cout << "Insert sort\n"; //output cout << "Before array: \n"; for(int i = 0; i < matSize; i++) { for(int j = 0; j < matSize; j++) { cout << mat[i][j] << "\t"; } cout << endl; } auto start1 = chrono::stea...